/*
 * @lc app=leetcode.cn id=241 lang=cpp
 *
 * [241] 为运算表达式设计优先级
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    // 什么时候试试dp
    vector<int> diffWaysToCompute(string expression) {
        vector<int> trans = transferInput(expression);
        vector<int> result = recursion(trans);
        return result;
    }
    vector<int> recursion(vector<int> input){        
        if (input.size() == 1){
            return input;
        }
        vector<int> result;
        int num = input.size()/2 + 1;
        for (int i=0;i<num-1;i++){
            vector<int>::const_iterator iter = input.begin();
            vector<int> leftVec(iter, iter+2*i+1);
            vector<int> rightVec(iter+2*(i+1), iter+2*(i+1)+2*(num-1-i)-1);
            vector<int> left = recursion(leftVec);
            vector<int> right = recursion(rightVec);
            int operation = input[2*i+1];
            // string leftString = expression.substr(0,2*i+1);
            // string rightString = expression.substr(2*(i+1),2*(num-1-i)-1);
            // vector<int> left = diffWaysToCompute(leftString);
            // vector<int> right = diffWaysToCompute(rightString);
            // char operation = expression[2*i+1];
            vector<int> subResult = computeSubs(left, right, operation);
            result.insert(result.end(), subResult.begin(), subResult.end());
        }
        return result;        
    }
    vector<int> transferInput(string expression){
        vector<int> result;
        int startIndex = 0;
        for (int i=0;i<expression.size();i++){
            if (expression[i]=='+'){
                int get = atoi(expression.substr(
                    startIndex, i-startIndex).c_str());
                result.emplace_back(get);
                result.emplace_back(-1);
                startIndex = i+1;
            }else if (expression[i]=='-'){
                int get = atoi(expression.substr(
                    startIndex, i-startIndex).c_str());
                result.emplace_back(get);
                result.emplace_back(-2);
                startIndex = i+1;
            }else if (expression[i]=='*'){
                int get = atoi(expression.substr(
                    startIndex, i-startIndex).c_str());
                result.emplace_back(get);
                result.emplace_back(-3);
                startIndex = i+1;
            }else if (i==expression.size()-1){
                int get = atoi(expression.substr(
                    startIndex, i+1-startIndex).c_str());
                result.emplace_back(get);
            }
        }
        return result;
    }
    vector<int> computeSubs(vector<int>& left, 
    vector<int>& right, int operation){
        // int lenghLeft = left.size();
        // int lenghRight = right.size();
        vector<int> result;
        for (int i : left){
            for (int j : right){
                result.emplace_back(compute(i, j, operation));
            }
        }
        return result;
    }
    int compute(int left, int right, int operation){
        // int operate = operation;
        switch (operation)
        {
        case -1:
            return left+right;
            break;
        case -2:
            return left-right;
            break;
        case -3:
            return left*right;
            break;
        default:
            return 0;
            break;
        }
    }
};
// int main(){
//     Solution mySolution;
//     string myString("2-1-1*111+11111-678798");
//     vector<int> trans = mySolution.transferInput(myString);
//     for (int i:trans){
//         printf("%d\n", i);
//     }
//     // mySolution.diffWaysToCompute("2-1-1");
//     // return 0;
// }
// @lc code=end

